#pragma comment (linker, "/STACK:100000000")
#include "testlib.h"
#include <stdio.h>
#include <string>
#include <vector>

using namespace std;

#define forn(i, n) for (int i = 0; i < (int)(n); i++)

typedef long long ll;

#define N 100010

string ss;

int n, a[N][26], u[N], v[N];
char s[N];
vector <int> m[N];
vector <char> mc[N];

ll _hs[N], _h[N], _deg[N], P = 239017;
int _to[N], _len[N], _used[N], _mem[N], _mem2[N];

ll A=1992919, B=18181971;

int next()
{
	A=(A*13166771+B)%1000000007;
	B=(B*67771+A)%1000000007;
	return A;
}
void shuffle(int *a, int n)
{
	for(; n; swap(a[n-1], a[next()%n]), n--);
}
bool dfs(int i)
{
	int j;
	u[i]=1;
	for(j=0; j<(int)m[i].size(); j++)
		if(u[m[i][j]]==1) return 1;
		else if(!u[m[i][j]] && dfs(m[i][j])) return 1;
	u[i]=2;
	return 0;
}

void precalc( int v )
{
  if (_used[v] == 1)
    return;
  _used[v] = 1;
  forn(i, m[v].size())
    precalc(m[v][i]);
  if (m[v].size() == 1U)
  {
    int next = m[v][0];
    char ch = mc[v][0];
    _len[v] = _len[next] + 1;
    _h[v] = ch * _deg[_len[next]] + _h[next];
    _to[v] = _to[next];
    //printf("hash[%d] = %I64u [len = %d, to = %d]\n", v, _h[v], _len[v], _to[v]);
  }
  else
  {
    _to[v] = v, _len[v] = 0, _h[v] = 0;
    //printf("hash[%d] = 0\n", v);
  }
}

void fail( int x )
{
    quitf(_wa, "suffix started from %d (%s) is not accepted", x + 1, __testlib_part(ss.substr(x)).c_str());
}

inline ll _substr( int l, int r ) // [l, r)
{
  return _hs[r] - _hs[l] * _deg[r - l];
}

void _gen()
{
  int x = 0, y = n - 2, i = 0;
  while (i < n - 1)
  {
    v[i++] = x++;
    if (i < n - 1)
      v[i++] = y--;
  }
}

int main(int argc, char * argv[])
{
    _deg[0] = 1;
    forn(i, N - 1)
      _deg[i + 1] = _deg[i] * P;

    registerTestlibCmd(argc, argv);
    int k, i, j, l, q;
	string c;
	ss=inf.readWord();
	n=ouf.readInt();
	if(n!=(int)ss.size()+1) quitf(_wa, "number of nodes expected %d, found %d", ss.size()+1, n);
	k=ouf.readInt();
	if(k<0 || k>2*n) quitf(_wa, "nuber of edges must be in range %d, %d, found %d", 0, 2*n, k);
	for(l=k; k--; )
	{                             
		i=ouf.readInt();
		if(i<1 || i>n) quitf(_pe, "invalid node %d", i);
		j=ouf.readInt();
		if(j<1 || j>n) quitf(_pe, "invalid node %d", j);
		m[i-1].push_back(j-1);
		c=ouf.readWord();
		if(c.size()!=1 || c[0]<'a' || c[0]>'z') quitf(_pe, "invalid symbol %s", c.c_str());
		a[i-1][c[0]-'a']=j-1;
		mc[i-1].push_back(c[0]-'a');
	}
	
	precalc(0);
	_hs[0] = 0;
	forn(i, n - 1)
	  _hs[i + 1] = _hs[i] * P + (ss[i] - 'a');
	
	for(i=0; i<n; i++)
		if(!u[i] && dfs(i)) quitf(_wa, "there is a loop");
	_gen();
	if (n > 100)
      shuffle(v+100, n-1);
/*
    forn(i, n - 1)
      printf("%d ", v[i]);
    puts("");
*/
	q=0;
	for(i=0; i<n-1; s[i]=ss[i]-'a', i++)
	    ;
	memset(_mem, -1, sizeof(_mem));
	memset(_mem2, -1, sizeof(_mem2));
	for(i=0; i<n-1 && q<(int)1e8; i++)
	{
	    int pos = v[i], k = 0;
	    for (; pos != n - 1; q++)
	    {
	       if (_mem[k] == pos)
	         break;
	       _mem[k] = pos;
	       if (_mem2[pos] == k)
	         break;
	       _mem2[pos] = k;
	       if (m[k].size() == 1U && pos + _len[k] <= n - 1)
	       {
	           if (_substr(pos, pos + _len[k]) != _h[k])
	           {
	             //printf("v=%d: %d --> %d : in automaton hash = %I64u, original hash = %I64u\n", k, pos, pos + _len[k], _h[k],
	             //  _substr(pos, pos + _len[k]));
     	         fail(v[i]);
     	       }
     	       pos += _len[k];
     	       k = _to[k];
	       }
	       else
	       {
    	       if (!a[k][(int)s[pos]])
     	         fail(v[i]);
     	       else
     	         k = a[k][(int)s[pos++]];
     	   }
       }
/*
		for(k=0, j=v[i]; j<n-1; q++, j++)
			if(!a[k][(int)s[j]]) quitf(_wa, "suffix %s is not accepted", __testlib_part(ss.substr(i)).c_str());
			else k=a[k][(int)s[j]];
*/
	}
	quitf(_ok, "%d nodes, %d edges, %d suffixes are checked, q = %d", n, l, i, q);
}